package com.ztom.top100;

/**
 * 最长回文子串
 * <p>
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 *
 * @author ZhangTao
 */
public class Code05LongestPalindrome {

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        if (s.length() == 1) {
            return s;
        }
        // 生成 manacher 串
        char[] str = getManacherStr(s);
        // 最长回文半径数组
        int[] pArr = new int[str.length];
        // 当前最长回文半径右边界
        int r = -1;
        // 当前最长回文半径中心位置
        int c = -1;
        // 记录最大长度 和 中心下标
        int[] res = new int[2];
        for (int i = 0; i < str.length; i++) {
            pArr[i] = i <= r ? Math.min(r - i + 1, pArr[2 * c - i]) : 1;

            while (i - pArr[i] >= 0 && i + pArr[i] < str.length) {
                if (str[i - pArr[i]] == str[i + pArr[i]]) {
                    pArr[i]++;
                } else {
                    // 不能扩, 直接跳出
                    break;
                }
            }
            // 记录新的最长半径右边界
            if (i + pArr[i] - 1 > r) {
                r = i + pArr[i] - 1;
                c = i;
            }
            res[0] = pArr[i] > res[1] ? i : res[0];
            res[1] = Math.max(res[1], pArr[i]);
        }
        return new String(str, res[0] - res[1] + 1, 2 * res[1] - 1).replace("#", "");
    }

    /**
     * "123" ==> "#1#2#3#"
     *
     * @param s
     * @return
     */
    private char[] getManacherStr(String s) {
        char[] chars = s.toCharArray();
        char[] manacher = new char[2 * chars.length + 1];
        for (int i = 0; i < manacher.length; i++) {
            manacher[i] = (i & 1) == 0 ? '#' : chars[i / 2];
        }
        return manacher;
    }
}
